package leetcode.biweekly.week103;

import java.util.Arrays;
import java.util.TreeMap;
import java.util.TreeSet;

//Solution4Test
public class Solution5 {

	public long countOperationsToEmptyArray(int[] nums) {
		int n = nums.length;
		Record record = new Record(n);
		Integer[] idx = new Integer[n];
		for (int i = 0; i < n; i++) {
			idx[i] = i + 1;
		}
		TreeSet<Integer> ts = new TreeSet<>();
		for(int num : nums) {
			ts.add(num);
		}
		TreeMap<Integer, Integer> tm = new TreeMap<>();
		int id = 1;
		for (int num : ts) {
			tm.put(num, id++);
		}
		for (int i = 0; i < idx.length; i++) {
			nums[i] = tm.get(nums[i]);
		}
		Arrays.sort(idx, (a, b) -> nums[a - 1] - nums[b - 1]);
		long ans = 0;
		for (int i = 0; i < n; i++) {
			int num = nums[i];
			int l = record.query(num);
			ans += num - l;
			record.add(num);
		}
		return ans;
	}

	class Record {
		int len;
		int[] arr;

		public Record(int n) {
			len = n + 2;
			arr = new int[len];
		}

		public void add(int num) {
			while (num < len) {
				arr[num]++;
				num += this.lowbit(num);
			}
		}

		public void sub(int num) {
			while (num < len) {
				arr[num]--;
				num += this.lowbit(num);
			}
		}

		public int query(int num) {
			int ans = 0;
			while (num > 0) {
				ans += arr[num];
				num -= this.lowbit(num);
			}
			return ans;
		}

		public int lowbit(int num) {
			return num & -num;
		}
	}

}
